package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 回溯算法组合
 */
public class Solution26 {
    //定义二维数组
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    //定义一维数组
    public List<List<Integer>> combine(int n, int k) {
        backtarcking(n,k,1);
        return result;
    }

    //n 代表从1到n之间的范围
    public void backkArcking(int n , int k , int startIndex){
        if(path.size() == k){
            //result.add(new ArrayList<>(path));

            result.add(new ArrayList<>(path));
            return;
        }
        //n - (k - path.size()) + 1 代表剪枝操作
        //i <= n 代表普通操作
        for(int i = startIndex ; i <= n - (k - path.size()) + 1 ; i++){
            path.add(i);
            backtarcking(n,k,i + 1);
            path.removeLast();
        }
    }
}
